#include <iostream>
#include <cstring>
#include <vector>
#define INF 1<<20
using namespace std;
struct Edge
{
    int start;
    int end;
    int capacity;
    Edge(int s,int e,int c){start=s;end=e;capacity=c;}
};
//图类,使用邻接矩阵实现，这里只考虑了简单无向加权图
class Graph
{
    private:
        int V;//图包含顶点数
	    int ** matrix;  //保存邻接矩阵
	    bool dfs(int s,int t,vector<Edge> &path,bool * used);  //递归找路
	    bool find_path(int s,int t,vector<Edge> &path);    //找到一条从s到t的增广路径
	public:
        //根据点数构造图
		Graph(int V);
        //析构函数
        ~Graph();
        //根据起点和终点构造一条边
        void addEdge(int start,int end,int capacity=1);
        //打印图信息
        void printMap();
        //ford_fulkerson算法
        int ford_fulkerson(int s,int t);
};
